package main

import (
	"fmt"
	"math"
)

// 已知数组 A, B, 如果 A 中元素在 B 数组存在，打印出这个元素的下标，B 数组是不重复的.
// Input: [5, 3, 1, 5, 4] [5, 3]
// Output: [0, 1, 3]

func main() {
	a := []int{5, 3, 1, 5, 4}
	b := []int{5, 3}
	_ = find(a, b)
	three()
	//log.Print(res)
}

// 从上到下找到最短路径（n个数字之和最小,n为矩阵的行数），可以从第一行中的任何元素开始，只能往下层走，同时只能走向相邻的节点，例如图中第一排 2 只能走向 第二排的 7、3；第二排的 7 可以走向第三排的 6、2、9
//
// | 5    | 8    | 1    | 2    |
// | 4    | 1    | 7    | 3    |
// | 3    | 6    | 2    | 9    |
//
// Input: [
//     [5, 8, 1, 2],
//     [4, 1, 7, 3],
//     [3, 6, 2, 9]
// ]
// Output: 4

func three() {
	matrix := [][]int{
		{5, 8, 1, 2},
		{4, 1, 7, 3},
		{3, 6, 2, 9},
	}
	fmt.Println(minPath(matrix))
}

func minPath(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])
	dp := make([][]int, rows)
	for i := range dp {
		dp[i] = make([]int, cols)
	}
	dp[0] = grid[0]
	for i := 1; i < rows; i++ {
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}
	for j := 1; j < cols; j++ {
		dp[0][j] = dp[0][j-1] + grid[0][j]
	}
	for i := 1; i < rows; i++ {
		for j := 1; j < cols; j++ {
			dp[i][j] = int(math.Min(float64(dp[i-1][j]), float64(dp[i][j-1])))
		}
	}
	return dp[rows-1][cols-1]
}

func find(a, b []int) []int {
	indexMap := make(map[int]struct{})
	for _, v := range b {
		indexMap[v] = struct{}{}
	}
	var res []int
	for i, v := range a {
		if _, ok := indexMap[v]; ok {
			res = append(res, i)
		}
	}
	return res
}

// 现在数据库有一张表，用来存储一个多叉树，
// id为主键，pid 表示父节点的 id，
// 已知 "-1" 表示根节点，
// 现在要求打印出从根节点到每个子节点的路径（可以是无序的）。
//
// | id      | pid    |
// |---------|--------|
// | "A"     | "-1"   |
// | "A-1"   | "A"    |
// | "A-2"   | "A"    |
// | "A-3"   | "A"    |
// | "A-2-1" | "A-2"  |
// | "A-2-2" | "A-2"  |
// | "A-2-3" | "A-2"  |
//
// Output:
//   "/A"
//   "/A/A-3"
//   "/A/A-2"
//   "/A/A-1"         // （结果可以是无序的）
//   "/A/A-2/A-2-2"   // （结果可以是无序的）
//   "/A/A-2/A-2-1"
//   "/A/A-2/A-2-3"
//

type Node struct {
	ID  string
	PID string
}

var (
	nodes = []Node{
		{"A", "-1"},
		{"A-1", "A"},
		{"A-2", "A"},
		{"A-3", "A"},
		{"A-2-1", "A-2"},
		{"A-2-2", "A-2"},
		{"A-2-3", "A-2"},
	}
	m map[string]Node
)

func tow() {
	convert(nodes)

	fmt.Println(nodes)
}

func convert(nodes []Node) {
	nodeMap := make(map[string]Node)
	for _, node := range nodes {
		nodeMap[node.ID] = node
	}
	m = nodeMap
}

//func findPath(nodeMap map[string]Node, node Node) {
//	var path []string
//	for {
//		path = append([]string{}, path...)
//		if !node.PID {
//
//		}
//	}
//}
